package com.canopys.study.open.test.algorithm.backtracking;

/**
 * @Author: Canopys
 * @Descrption:
 * @Date: Created in 22:42 2020/12/3
 * @Modified By:
 */
public class ZeroOne {
    public static int max = 0;

    //不对，这个貌似是贪心算法，不是回溯算法
    public static int wight(int n, int[] a, int W) {
        if (n < 0 || W - a[n] < 0) {
            return 0;
        }
        if (W - a[n] == 0 || n == 0) {
            return a[n];
        }

        int res = wight(n - 1, a, W);
        if (a[n] <= W) {
            res = Math.max(res, wight(n - 1, a, W - a[n]) + a[n]);
        }
        max = Math.max(max, res);
        return res;
    }

    public static void wight2(int n, int[] a, int cw, int W) {
        if (n == a.length  || cw == W) {  // n == a.length 考察完了所以元素，cw == W 背包已经满了
            max = Math.max(cw, max);
            return;
        }
        wight2(n + 1, a, cw, W);  // 不装
        if (cw + a[n] <= W) {
            wight2(n + 1, a, cw + a[n], W);  // 装
        }
        return;
    }


    public static void main(String[] args) {
        int[] a = new int[] {2, 2, 4, 6, 3};
        int n = a.length - 1;
        int W = 9;
        System.out.println(wight(n, a, W));
        System.out.println(max);
        max = 0;
        wight2(0, a, 0, W);
        System.out.println(max);
    }
}
